#define _CRT_SECURE_NO_WARNINGS 1

#include<vector>
#include<string>
#include<iostream>
using namespace std;

class Solution
{
public:
    vector<string> letterCombinations(string digits)
    {
        vector<string> v(9);
        v[0] += "abc";
        v[1] += "def";
        v[2] += "ghi";
        v[3] += "jkl";
        v[4] += "mno";
        v[5] += "pqrs";
        v[6] += "tuv";
        v[7] += "wxyz";

        vector<int> tmp(4);
        int size = 1;
        for (int i = 0; i < digits.size(); ++i)
        {
            tmp.push_back(digits[i] - '2');
            size *= v[digits[i] - '0'].size();
        }

        vector<string> ret(size);
        
        int i = 0;
        int k = 0;
        size /= v[tmp[0]].size();
        while (size > 1)
        {
            for (i = 0; i < tmp.size(); ++i)
            {
                for (int j = 0; j < v[tmp[i]].size(); ++j)
                {
                    ret[k++] += v[tmp[i]][j];
                    if (k == ret.size())
                    {
                        k = 0;
                    }
                }
            }
            size /= v[tmp[i]].size();
        }


        //for (int i = 0; i < ret.size(); ++i)
        //{
        //    reverse(ret[i].begin(), ret[i].end());
        //}

        return ret;
    }
};

int main()
{
    string s1("23");
    Solution ss1;
    vector<string> v = ss1.letterCombinations(s1);
    std::vector<string>::iterator it = v.begin();
    while (it != v.end())
    {
        cout << *it << endl;
        ++it;
    }

    return 0;
}